package leetcode.code0909;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int snakesAndLadders(int[][] board) {
		int n = board.length;
		int[][] nums = new int[n][n];
		for (int i = n, row = 0; i >= 1; i--, row++) {
			if ((i & 1) == 1) {
				int start = i == 1 ? 1 : (i - 1) * n + 1;
				for (int col = 0; col < n; col++) {
					nums[row][col] = start++;
				}
			} else {
				int start = i * n;
				for (int col = 0; col < n; col++) {
					nums[row][col] = start--;
				}
			}
		}
		int[] hash = new int[n * n + 1];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int cur = board[i][j];
				if (cur != -1) {
					hash[nums[i][j]] = cur;
				}
			}
		}
		int ans = 0;
		Queue<Integer> queue = new LinkedList<>();
		queue.add(1);
		boolean[] been = new boolean[n * n + 1];
		been[1] = true;
		while (!queue.isEmpty()) {
			ans++;
			int size = queue.size();
			while (size > 0) {
				int cur = queue.poll();
				for (int i = cur + 1; i <= Math.min(cur + 6, n * n); i++) {// i = cur + 1
					if (!been[i]) {
						been[i] = true;
						int to = i;
						if (hash[i] != 0) {
							to = hash[i];
						}
						if (i == n * n || to == n * n) {// to也有可能是直达
							return ans;
						}
//						been[to] = true; 跳跃的目的地上可能有更快的抵达方式，因为不能连跳，所以这里算作抵达的话，可能错过从这里开始的最快方式
						queue.add(to);
					}
				}
				size--;
			}
		}
		return been[n * n] ? ans : -1;
	}

	@Override
	public void debug4() {

		H.compare(-1, this.snakesAndLadders(H.str2array1("[[1,1,-1],[1,1,1],[-1,1,1]]")));
		H.compare(4, this.snakesAndLadders(H.str2array1(
				"[[-1,-1,27,13,-1,25,-1],[-1,-1,-1,-1,-1,-1,-1],[44,-1,8,-1,-1,2,-1],[-1,30,-1,-1,-1,-1,-1],[3,-1,20,-1,46,6,-1],[-1,-1,-1,-1,-1,-1,29],[-1,29,21,33,-1,-1,-1]]")));
		H.compare(4, this.snakesAndLadders(H.str2array1(
				"[[-1,-1,-1,46,47,-1,-1,-1],[51,-1,-1,63,-1,31,21,-1],[-1,-1,26,-1,-1,38,-1,-1],[-1,-1,11,-1,14,23,56,57],[11,-1,-1,-1,49,36,-1,48],[-1,-1,-1,33,56,-1,57,21],[-1,-1,-1,-1,-1,-1,2,-1],[-1,-1,-1,8,3,-1,6,56]]")));
		H.compare(1, this.snakesAndLadders(H.str2array1("[[-1,-1,-1],[-1,9,8],[-1,8,9]]")));
		H.compare(1, this.snakesAndLadders(H.str2array1("[[-1,-1],[-1,3]]")));
		H.compare(4, this.snakesAndLadders(H.str2array1(
				"[[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
